A database may comprise a set of tables, each table having one or more columns and a plurality of rows. Each table may be indexed using a B-Tree. A B-Tree is a tree data structure which can be used to identify selected rows of a single table based on certain keys. The time required to insert, delete or search for keys in a B-Tree varies logarithmically with the number of data elements in the B-Tree.
Some databases employ a variation of the B-Tree known as a B+Tree. A B+Tree differs from a standard B-Tree in that all row identifiers are stored in the leaves of a B+Tree.
Databases often include a number of related or “joined” tables. Two tables are joined if each of the tables includes one or more columns that are related to corresponding columns in the other one of the tables. When such a database is queried to locate all rows having a particular data element (referred to as a “key”), some prior art systems execute a join for all of the tables of the database to produce a join table. A join is an operation wherein all of the rows of all of the tables of the database are scanned to identify rows containing the key specified by the query. Performing join operations can be time consuming.
Performance has been always a challenge for relational database systems. A major problem with relational database systems is that a good relationship schema requires many tables having columns in common between them. Accordingly, it is often necessary to calculate many joins to execute queries.
A database administrator typically spends a lot of time to tune the structure of a database to permit queries to be executed efficiently. In order to reduce the number of joins required to execute queries, some database schemas avoid the use of normal forms such as the Boyce-Codd normal form (BCNF). One prior art example of such a schema is known as the “Star Schema”. The Star Schema was developed to simplify joins. A database organized according to the Star Schema typically has one main table or “fact table”, and a plurality of other tables or “dimension tables” which are each in direct join with the fact table.
Another example of a prior art system for dealing with joins is the bitmap join index originated by the Oracle Corporation of Redwood Shores, Calif. A bitmap join index has pre-joined the tables. Queries can quickly retrieve row ID lists of matching table rows in all tables by consulting the bitmap join index. Some restrictions on using the bitmap join index include:                indexed columns must be of low cardinality;        SQL queries must not have any references in their WHERE clauses to data columns that are not contained in the index; and,        updating bitmap join indexes involves substantial overhead.In practice, bitmap join indexes are typically rebuilt each evening to incorporate data changes made by daily batch load jobs. Accordingly, bitmap join indexes may be unsuitable for databases that are modified during the processing day.        
The inventor has developed efficient systems to make join tables available for a database without the need to calculate them each time the database is queried, and without avoiding the use of normal forms or limiting the number of distinct values in the columns of the tables.